package leetcode.code1986;

import leetcode.IDebug;
import leetcode.helper.H;

public class Solution implements IDebug {

	int n, limit, sessionTime;
	int[] tasks;

	public int minSessions(int[] tasks, int sessionTime) {
		n = tasks.length;
		limit = (1 << n) - 1;
		this.sessionTime = sessionTime;
		this.tasks = tasks;
		Integer[][] dp = new Integer[1 << n][sessionTime + 1];
		return this.find(0, sessionTime, dp);
	}

	// done 完成任务状态，剩余时间
	private int find(int done, int restTime, Integer[][] dp) {
		if (limit == done) {
			return 1;
		}
		if (dp[done][restTime] != null) {
			return dp[done][restTime];
		}
		int rest = limit ^ done;
		int ans = Integer.MAX_VALUE;
		// 剩下的任务中，有没有能一起做的
		for (int i = 0; i < tasks.length && restTime > 0; i++) {
			int index = (1 << i);
			if ((index & rest) > 0 && this.tasks[i] <= restTime) {
				ans = Math.min(ans, this.find(done | index, restTime - this.tasks[i], dp));
			}
		}
		// 没有能一次做的，完成一次，重新做
		if (ans == Integer.MAX_VALUE) {
			ans = Math.min(ans, this.find(done, this.sessionTime, dp) + 1);
		}
		dp[done][restTime] = ans;
		return ans;
	}

	@Override
	public void debug4() {
		H.compare(4, this.minSessions(H.str2array3("[1,1,2,3,4,5,7,8]"), 8));
		H.compare(2, this.minSessions(H.str2array3("[1,2,3]"), 3));
		H.compare(2, this.minSessions(H.str2array3("[3,1,3,1,1]"), 8));
		H.compare(1, this.minSessions(H.str2array3("[1,2,3,4,5]"), 15));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
//		System.out.println(Integer.toBinaryString(8));
//		System.out.println(Integer.toBinaryString(254));
//		System.out.println(Integer.toBinaryString(254 & 8));
	}

}
